题目 | 难度 |
---|---|
剑指 Offer 06. 从尾到头打印链表 | 简单 |
剑指 Offer 18. 删除链表的节点 | 简单 |
剑指 Offer 24. 反转链表 | 简单 |
剑指 Offer 35. 复杂链表的复制 | 中等 |
剑指 Offer 36. 二叉搜索树与双向链表 | 中等 |
剑指 Offer 52. 两个链表的第一个公共节点 | 简单 |
# 1. 从尾到头打印链表
题目
输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。
**思路:**先进栈再出栈
使用一个辅助栈,遍历链表时,先将元素放入辅助栈。
最后从尾遍历辅助栈。
时间、空间复杂度都是O(n)
var reversePrint = function (head) {
let array = []
while (head !== null) {
array.unshift(head.val)
head = head.next
}
return array
};
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
输入:head = [1,3,2]
输出:[2,3,1]
1
2
2
# 2. 删除链表的节点
题目
给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。
返回删除后的链表的头节点。
思路:
- 定义虚拟节点,用指针遍历链表
- 如果下一个值等于
val
,则删除下一个值 - 使用ES6的
?.
运算符,判断p
是否存在
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
const deleteNode = (head, val) => {
// 定义虚拟节点
const res = new ListNode(null);
// 虚拟节点连接到head
res.next = head;
// 定义p指针,最开始指向虚拟节点的头部
let p = res;
// 遍历链表
while (p?.next) {
// 如果下一个值等于val,则删除下一个值
if (p.next.val === val) p.next = p.next.next;
p = p.next;
}
return res.next;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
1
2
3
2
3
# 3. 反转链表
题目
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
1
2
2
思路1:
在遍历链表时,将当前节点的 next
指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用。
var reverseList = function(head) {
let prev = null;
let curr = head;
while (curr) {
const temp = curr.next;//存储下一个节点
curr.next = prev;//更改当前节点的next=上一个节点
prev = curr;//改变pre
curr = temp;//改变curr 继续循环
}
return prev;
};
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 4. 复杂链表的复制
题目
请实现 copyRandomList
函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next
指针指向下一个节点,还有一个 random
指针指向链表中的任意节点或者 null
。
思路:
- 遍历旧链表,用
Map
复制各节点值。Map
的键为旧节点,值为新节点的值。 - 再次遍历旧链表,复制各节点的连接关系
const copyRandomList = head => {
const map = new Map();
// 第一次遍历,复制节点值
let p = head;
while (p) {
map.set(p, new Node(p.val));
p = p.next;
}
// 第二次遍历,复制节点关系
p = head;
while (p) {
map.get(p).next = map.get(p.next) || null;
map.get(p).random = map.get(p.random) || null;
p = p.next;
}
return map.get(head);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 5. 二叉搜索树与双向链表
思路:
- 因为是二叉搜索树,采用中序遍历刚好满足顺序条件
- 中序遍历时,先判断
pre
是否有值,若无值,则表示当前是表头节点,赋值为head
;若有值,更新指针,双向连接(pre.right = cur;cur.left = pre;
) - 更新
pre
,将当前节点作为一下个节点的上一个节点 - 最后要将头部节点和尾部节点相连
const treeToDoublyList = root => {
const dfs = cur => {
if (!cur) return;
dfs(cur.left);
if (!pre) {
// pre为空,正在访问表头节点,赋为head
head = cur;
} else {
// pre有值,更新指针,双向连接
pre.right = cur;
cur.left = pre;
}
// 更新pre,将当前节点作为一下个节点的上一个节点
pre = cur;
dfs(cur.right);
};
let pre, head;
if (!root) return;
dfs(root);
// 首尾相连
head.left = pre;
pre.right = head;
return head;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 6. 两个链表的第一个公共节点
题目
输入两个链表,找出它们的第一个公共节点。
如下面的两个链表**:**
在节点 c1 开始相交。
示例 :
思路:
- 我们使用两个指针
pA
,pB
分别指向两个链表headA
,headB
的头结点,然后同时分别逐结点遍历 - 当
pA
到达链表headA
的末尾时,重新定位到链表headB
的头结点; - 当
pB
到达链表headB
的末尾时,重新定位到链表headA
的头结点。 - 当它们相遇时,所指向的结点就是第一个公共结点。
var getIntersectionNode = function (headA, headB) {
let pA = headA;
let pB = headB;
while (pA !== pB) {
pA = pA === null ? headB : pA.next;
pB = pB === null ? headA : pB.next;
// if (pA === null) {
// pA = headB;
// } else {
// pA = pA.next;
// }
// if (pB === null) {
// pB = headA;
// } else {
// pB = pB.next;
// }
}
return pA;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19